public class UnionFindMax {
	int[] id;
	int[] sz;
	int[] rootMax;

	public UnionFindMax(int n) {
		id = new int[n];
		sz = new int[n];
		rootMax = new int[n];
		
		for (int i = 0; i < n; ++i) {
			id[i] = i;
			sz[i] = 1;
			rootMax[i] = i;
		}
	}

	public void union(int a, int b) {
		int roota, rootb;
		roota = root(a);
		rootb = root(b);

		if (roota == rootb)
			return;

		if (sz[roota] >= sz[rootb]) {
			sz[roota] += sz[rootb];
			id[rootb] = roota;
			if (rootMax[roota] < rootMax[rootb]) {
				rootMax[roota] = rootMax[rootb];
			}
		} else {
			sz[rootb] += sz[roota];
			id[roota] = rootb;
			if (rootMax[roota] > rootMax[rootb]) {
				rootMax[rootb] = rootMax[roota];
			}
		}
	}

	public int root(int p) {
		while (p != id[p]) {
			p = id[p];
		}
		return p;
	}
	
	public int find(int p) {
		return rootMax[root(p)];
	}
	public boolean connect(int a, int b) {
		int roota, rootb;
		roota = root(a);
		rootb = root(b);

		return roota == rootb ? true : false;
	}

	public static void main(String[] args) {
		UnionFindMax uf = new UnionFindMax(10);
		uf.union(3, 4);
		uf.union(5, 6);
		uf.union(6,  3);
		System.out.println(uf.connect(4, 5));
		System.out.println(uf.find(3));
	}

}
